package com.hws.leetcode.Day_01_12;

import java.util.Arrays;

/**
 * ClassName:leetcode_334
 * Package:com.hws.leetcode.Day_01_12
 * Description:
 *
 * @ date:2022/1/12 20:04
 * @ author:hws
 */
public class leetcode_334 {

    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length < 3) {
            return false;
        }
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int len = 1;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            if (num > dp[len - 1]) {
                dp[len++] = num;
                if (len >= 3) {
                    return true;
                }
                continue;
            }
            int left = 0, right = len - 1;
            while (left < right) {
                int mid = (right - left) / 2 + left;
                if (dp[mid] >= num) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            dp[right] = num;
            if (len >= 3) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        leetcode_334 lc = new leetcode_334();
        int[] nums = new int[]{1,2,9,4,5};
        System.out.println(lc.increasingTriplet(nums));
    }

}
